Java তে Trie এর ইমপ্লিমেন্টেশন

Trie (ট্রাই) হলো একটি বিশেষ ধরনের ডাটা স্ট্রাকচার যা মূলত প্যাটার্ন ম্যাচিং, ডিকশনারি অনুসন্ধান এবং স্ট্রিং সংক্রান্ত অপারেশন এর জন্য ব্যবহৃত হয়। এটি একটি নন-বিনারি গাছ (tree) যেখানে প্রতিটি নোড একটি চরিত্র (character) ধারণ করে, এবং পুরো স্ট্রিং (অথবা শব্দ) অনুসন্ধান বা সংরক্ষণ করার জন্য এটি একটি পথ তৈরি করে।

ট্রাই ডাটা স্ট্রাকচারটি সাধারনত স্ট্রিং স্টোরেজ এবং স্ট্রিং অনুসন্ধান এর জন্য ব্যবহৃত হয়। স্ট্রিংগুলির মধ্যে কমন প্রিফিক্সগুলো একত্রে স্টোর করার জন্য ট্রাই খুবই কার্যকরী, যেহেতু এটি একই প্রিফিক্সের জন্য একটাই নোড ব্যবহার করে।

Trie এর কার্যপ্রণালী

ট্রাই ডাটা স্ট্রাকচারের প্রধান সুবিধা হলো:

• স্ট্রিং অনুসন্ধান: স্ট্রিং বা শব্দের মধ্যে দ্রুত অনুসন্ধান।
• কমন প্রিফিক্স সংরক্ষণ: ট্রাই একাধিক শব্দের কমন প্রিফিক্সের জন্য একটাই নোড ব্যবহার করে, যার ফলে মেমরি ব্যবহার কমে।
• প্রিফিক্স অনুসন্ধান: এটি প্রিফিক্স অনুসন্ধান করার জন্য খুবই কার্যকরী।

Trie এর কাঠামো

1. Root Node: ট্রাইয়ের মূল নোড, এটি কোনো শব্দ ধারণ করে না। এটি সব শব্দের জন্য একটি স্টার্টিং পয়েন্ট।
2. Child Node: প্রতিটি নোডের একটি বা একাধিক চাইল্ড নোড থাকতে পারে, এবং প্রতিটি চাইল্ড নোড একটি চরিত্র ধারণ করে।
3. Leaf Node: এটি এমন একটি নোড যা একটি সম্পূর্ণ শব্দ বা স্ট্রিং নির্দেশ করে।

Java তে Trie ইমপ্লিমেন্টেশন

ট্রাই ইমপ্লিমেন্টেশনের জন্য প্রথমে একটি TrieNode ক্লাস তৈরি করা হয়, যা প্রতিটি নোডের জন্য একটি চরিত্র এবং তার চাইল্ড নোডের লিস্ট ধারণ করবে। এরপর একটি Trie ক্লাস তৈরি করা হয় যা ট্রাই এর অপারেশন যেমন insert, search, এবং startsWith ইমপ্লিমেন্ট করবে।

১. TrieNode ক্লাস

class TrieNode {
    TrieNode[] children;  // চাইল্ড নোডের জন্য অ্যারে
    boolean isEndOfWord;  // এটি একটি পূর্ণ শব্দ কিনা

    // কন্সট্রাক্টর
    public TrieNode() {
        children = new TrieNode[26];  // ইংরেজি বর্ণমালার ২৬টি অক্ষর
        isEndOfWord = false;  // শুরুতে কোন শব্দ নেই
    }
}

২. Trie ক্লাস

public class Trie {
    private TrieNode root;

    // কন্সট্রাক্টর
    public Trie() {
        root = new TrieNode();  // ট্রাইয়ের মূল নোড তৈরি
    }

    // শব্দ ইনসার্ট করা
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';  // 'a' থেকে 'z' পর্যন্ত ইনডেক্স
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();  // নতুন নোড তৈরি
            }
            node = node.children[index];  // চাইল্ড নোডে যাওয়া
        }
        node.isEndOfWord = true;  // শব্দ শেষ হওয়া
    }

    // শব্দটি ট্রাই-এ আছে কিনা তা চেক করা
    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return false;  // শব্দ পাওয়া যায়নি
            }
            node = node.children[index];
        }
        return node.isEndOfWord;  // যদি শব্দের শেষের নোড 'true' হয়, তবে শব্দটি ট্রাই-এ আছে
    }

    // কোনো শব্দের প্রিফিক্স রয়েছে কিনা তা চেক করা
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return false;  // প্রিফিক্স পাওয়া যায়নি
            }
            node = node.children[index];
        }
        return true;  // প্রিফিক্স পাওয়া গেছে
    }
}

৩. Main Method Example

public class Main {
    public static void main(String[] args) {
        Trie trie = new Trie();
        
        trie.insert("apple");
        trie.insert("app");
        trie.insert("banana");

        // শব্দটি খুঁজে পাওয়া
        System.out.println(trie.search("apple"));  // true
        System.out.println(trie.search("app"));    // true
        System.out.println(trie.search("banana")); // true
        System.out.println(trie.search("bat"));    // false

        // প্রিফিক্স চেক করা
        System.out.println(trie.startsWith("ban")); // true
        System.out.println(trie.startsWith("bana")); // true
        System.out.println(trie.startsWith("bat"));  // false
    }
}

আউটপুট:

true
true
true
false
true
true
false

সারাংশ

Trie (ট্রাই) একটি বিশেষ ধরনের ডাটা স্ট্রাকচার যা স্ট্রিং বা শব্দের স্টোরেজ এবং অনুসন্ধান সমাধানে খুবই কার্যকরী। এটি সাধারণত স্ট্রিংস, প্রিফিক্স অনুসন্ধান, ডিকশনারি তৈরি, এবং প্যাটার্ন ম্যাচিং এর জন্য ব্যবহৃত হয়। ট্রাইয়ে insert, search, এবং startsWith এর মতো অপারেশন দ্রুত কার্যকরভাবে সম্পন্ন হয়, এবং এটি সাধারণত নেটওয়ার্কিং, সার্চ ইঞ্জিন, অটো কমপ্লিট ফিচার এবং স্পেল চেকিং এর মতো অ্যাপ্লিকেশনে ব্যবহৃত হয়।

• TrieNode: এটি প্রতিটি নোডের জন্য একটি ক্লাস যা চরিত্র এবং চাইল্ড নোড ধারণ করে।
• Trie: এটি ট্রাই ডাটা স্ট্রাকচারটি পরিচালনা করে এবং এর অপারেশনগুলোর জন্য ফাংশন সরবরাহ করে।

Trie অনেক কার্যকরী এবং মেমরি ইফিশিয়েন্ট স্ট্রিং স্টোরেজ মেকানিজম, যা দ্রুত শব্দের অনুসন্ধান, প্রিফিক্স অনুসন্ধান এবং অটো কমপ্লিট ফিচারগুলোতে ব্যবহৃত হয়।